#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>

using namespace std;


//回溯综合06：目标和
class Solution1 {
public:
    //int sum=0;
    int ret=0;
    //int path=0;
    int target=0;
    int findTargetSumWays(vector<int>& nums, int T) 
    {
        target=T;
        dfs(nums,0,0);
        return ret;
    }

    void dfs(vector<int>& nums,int path,int sum)
    {
        if(path==nums.size())
        {
            if(sum==target)
                ret++;
            return;
        }
        dfs(nums,path+1,sum+nums[path]);
        //--path;
        dfs(nums,path+1,sum-nums[path]);
        //--path;
    }
};



//回溯综合07：组合综合
class Solution2 {
public:
    int aim=0;
    vector<vector<int>> ret;
    vector<int> tmp;
    int sum=0;
    int size=0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        //sort(candidates.begin(),candidates.end());
        size=candidates.size();
        aim=target;
        dfs(candidates,0);
        return ret;    
    }

    void dfs(vector<int>& candidates,int pos)
    {
        if(sum==aim)
        {
            ret.push_back(tmp);
            return;
        }
        //if(sum+candidates[0]>aim)   return;
        if(sum>aim||pos>=size)   return;


        for(int i=pos;i<size;i++)
        {
            sum+=candidates[i];
            tmp.push_back(candidates[i]);
            dfs(candidates,i);
            sum-=candidates[i];
            tmp.pop_back();
        }
    }
};

//change name 20250707


void test1()
{
    vector<int> nums = { 1,1,1,1,1 };

    Solution1 SL;
    SL.findTargetSumWays(nums, 3);
}

int main()
{
    test1();
    return 0;
}